package com.likeycy.my.sort.cmp;

/**
 * @ClassName: InsertionSort3
 * @Description: 插入排序第三版优化：采用二分折半法
 * @Author: sodagreen
 * @Date: 2021/3/29 17:12
 * @Version: 1.0
 */
public class InsertionSort3<T extends Comparable<T>> extends Sort<T> {

    /*@Override
    protected void sort() {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int begin = 1; begin < array.length; begin++) {
            T t = array[begin];
            int insertIndex = search(begin);
            for (int i = begin; i > insertIndex; i--) {
                array[i] = array[i -1];
            }
            array[insertIndex] = t;
        }
    }*/


    /**
     * 拆分方法，让每个方法功能更清晰
     */
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            insert(begin, search(begin));
        }
    }

    /**
     * 将source位置的元素插入到dest位置
     *
     * @param source
     * @param dest
     */
    private void insert(int source, int dest) {
        T t = array[source];
        for (int i = source; i > dest; i--) {
            array[i] = array[i - 1];
        }
        array[dest] = t;
    }


    /**
     * 利用二分搜索法：从已排好序的数组中查找 index 位置元素的待插入位置
     * 已经排好序的数组的区间范围是 [0, index]
     *
     * @param index
     * @return
     */
    private int search(int index) {
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (comparatorToElements(array[index], array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}
